package com.easy.leetcode;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

/**
 * @ClassName Permute46
 * @Description 46. 全排列
 * @Author zheng
 * @Date 2021/11/30 10:03
 * @Version 1.0
 **/
public class Permute46 {
    /**
     * 返回结果
     **/
    List<List<Integer>> result = new ArrayList<>();
    /**
     * 路径
     **/
    List<Integer> path = new ArrayList<>();

    Map<Integer, Integer> tmp = new HashMap<>();

    public List<List<Integer>> permute(int[] nums) {
        backTracking(nums);
        //System.out.println(result.toString());
        return result;
    }

    public void backTracking(int[] nums) {
        //退出条件
        if (path.size() == nums.length) {
            result.add(new ArrayList<>(path));
            return;
        }


        for (Integer val : nums) {
            if (tmp.containsKey(val)) {
                continue;
            }
            tmp.put(val, val);
            path.add(val);
            backTracking(nums);
            tmp.remove(val);
            path.remove(path.size() - 1);
        }
    }

    public static void main(String[] args) {
        Permute46 permute46 = new Permute46();
        permute46.permute(new int[]{1, 3, 2});
        System.out.println(permute46.result.toString());
    }
}
